\label{sect:teoria}

Antes de que se explique concretamente lo realizado en este trabajo, es necesario
entender la teor'ia detr'as del mismo. Una parte importante de 'esta es lo que se
refiere a \emph{splines}, en particular \emph{splines naturales}. 
No se explicar'an aqu'i los conceptos previos necesarios para entender la teor'ia 
de splines. Para esto, se recomienda alg'un libro de an'alisis num'erico, como 
por ejemplo ~\cite{BurFa}.

\subsection{Splines}

El estudio de la aproximaci'on de una funci'on arbitraria por medio de un polinomio 
en un intervalo cerrado, muestra que la naturaleza oscilatoria de los polinomios 
de alto grado y la propiedad de que una fluctuaci'on en una parte peque'na de un 
intervalo puede ocasionar importantes fluctuaciones en todo el rango limita su 
utilizaci'on. 

Un procedimiento alterno consiste en dividir el intervalo en una serie de 
subintervalos, y en cada subintervalo construir un polinomio (generalmente) 
diferente de aproximaci'on. A esta forma de aproximar por medio de funciones se le 
conoce como \emph{aproximaci'on polin'omica fragmentaria}, o \emph{splines}.

La aproximaci'on polin'omica fragmentaria es la interpolaci'on lineal fragmentaria 
que consiste en unir una serie de puntos de datos
\[
\{(x_{0},f(x_{0})), (x_{1},f(x_{1})), \ldots, (x_{n},f(x_{n}))\}
\]
mediante una seria de segmentos de rectas.

La aproximaci'on por funciones lineales muestra una desventaja: no se tiene la 
seguridad de que haya diferenciabilidad en los extremos de los subintervalos, 
lo cual dentro de un contexto geom'etrico significa que la funci'on interpolante 
no es ``suave'' en dichos puntos. A menudo las condiciones f'isicas indican 
claramente que se requiere esa condici'on y que la funci'on de aproximaci'on 
debe ser continuamente diferenciable.

Otro procedimiento consiste en emplear un polinomio fragmentario del tipo Hermite. 
Por ejemplo, si los valores de la funci'on $f$ y de $f'$ se conocen en los puntos 
$x_{0} < x_{1} < \ldots < x_{n}$, podemos emplear el polinomio de Hermite de grado
3 en cada uno de los subintervalos $[x_{0}, x_{1}], [x_{1}, x_{2}], \ldots, 
[x_{n-1}, x_{n}]$ para obtener una funci'on continuamente diferenciable en el 
intervalo $[x_{0}, x_{n}]$. Si queremos determinar el polinomio c'ubico Hermite 
apropiado en determinado intervalo, basta calcular $H_{3}(x)$ para ese intervalo. 
Pueso que los polinomios interpolantes de Lagrange necesarios para calcular $H_{3}$ 
son de primer grado, podemos hacer el c'alculo sin gran dificultad. Sin embargo, 
para utilizar los polinomios fragmentarios de Hermite en la interpolaci'on general, 
necesitamos conocer la derivada de la funci'on que va a ser aproximada, lo cual 
muchas veces no es posible.

El tipo m'as simple de funci'on de polinomio fragmentario diferenciable en un 
intervalo entre $[x_{0}, x_{n}]$ es la funci'on obtenida al ajustar un polinomio 
cuadr'atico entre cada par consecutivo de nodos. Esto se hace construyendo una 
cuadr'atica en $[x_{0}, x_{1}]$ que concuerde con la funci'on $x_{0}$ y en $x_{1}$;
y as'i sucesivamente. Un polinomio cuadr'atico general tiene tres constantes 
arbitrarias - el t'ermino constante, el coeficiente $x$ y el coeficiente $x^{2}$ - 
y 'unicamente se requieren dos condiciones para ajustar los datos en los extremos 
de cada intervalo, por ello, existe flexibilidad que permite seleccionar la 
cuadr'atica de modo que la interpolante tenga una derivada continua en $[x_{0}, x_{n}]$. 
El problema de este procedimiento se presenta cuando hay que especificar las 
condiciones referentes a la derivada de la interpolante en los extremos $x_{0}$ y 
$x_{n}$. No hay constantes suficientes para cerciorarse de que se satisfagan 
las condiciones. 

La aproximaci'on polin'omica fragmentaria m'as com'un utiliza polinomios entre 
cada par consecutivo de nodos y recibe el nombre de \textbf{interpolaci'on de 
trazadores c'ubico} o \textbf{splines}. Un polinomio c'ubico general contiene 
cuatro constantes; as'i pues, el procedimiento del trazador c'ubico ofrece 
suficiente flexibilidad para garantizar que el interpolante no s'olo sea 
continuamente diferenciable en el intervalo, sino que adem'as tenga una segunda derivada continua en el intervalo. Sin embargo, en la construcci'on del trazador c'ubico 
no se supone que las derivadas del interpolante concuerdan con las de la funci'on, 
ni siquiera en los nodos.

De esta forma, se llega a una definici'on de spline.

Dada una funci'on $f$ definida en $[a, b]$ y un conjunto de nodos 
$a = x_{0} < x_{1} < \ldots < x_{n} = b$ un spline $S$ para $f$ es una funci'on 
que cumple con las condiciones siguientes:

\begin{enumerate}
	\item $S(x)$ es un polinomio c'ubico, denotado $S_{j}(x)$, en el intervalo 
	$[x_{j}, x_{j+1}]$ para cada $j = 0, 1, \ldots, n-1$.
	\item $S(x_{j}) = f(x_{j})$ para cada $j = 0, 1, \ldots, n$.
	\item $S_{j+1}(x_{j+1}) = S_{j}(x_{j+1})$ para cada $j = 0, 1, \ldots, n-2$.
	\item $S_{j+1}'(x_{j+1}) = S_{j}'(x_{j+1})$ para cada $j = 0, 1, \ldots, n-2$.
	\item $S_{j+1}''(x_{j+1}) = S_{j}''(x_{j+1})$ para cada $j = 0, 1, \ldots, n-2$.
	\item Una de la siguientes condiciones de frontera se satisface:
		\begin{enumerate}
			\item $S''(x_{0}) = S''(x_{n}) = 0$ (frontera libre o natural)
			\item $S'(x_{0}) = f'(x_{0})$ y $S'(x_{n}) = f'(x_{n})$ (frontera sujeta)
		\end{enumerate}
\end{enumerate}

Aunque los trazadores c'ubico se definen con otras condiciones de frontera, las 
condiciones dadas en (6) son suficientes en este caso. Cuando se presentan las 
condiciones frontera libre, el spline recibe el nombre de \emph{spline natural} 
y su gr'afica se aproxima a la forma que adoptar'ia una varilla larga y flexible 
si la hici'eramos pasar por los puntos 
${(x_{0},f(x_{0}), (x_{1},f(x_{1}), \ldots, (x_{n},f(x_{n})}$.

En t'erminos generales, en las condiciones de frontera sujeta se logran 
aproximaciones m'as exactas, ya que abarcan m'as informaci'on acerca de la 
funci'on. Pero para que se cumpla este tipo de condici'on de frontera, se requiere 
tener los valores de la derivada en los extremos o bien una aproximaci'on precisa 
de ellos. 

Si queremos construir el interpolante del trazador c'ubico de determinada 
funci'on $f$, aplicamos las condiciones de la definici'on a los polinomios c'ubicos:

\[
S_{j}(x) = a_{j} + b_{j} (x - x_{j}) + c_{j} (x - x_{j})^{2} + d_{j}(x - x_{j})^{3},
\]

para cada $j = 0, 1, \ldots, n-1$.

Est'a claro que 
\[
S_{j}(x) = a_{j} = f(x_{j})
\]

y se aplica la condici'on (3),

\[
a_{j+1} = S_{j+1}(x_{j+1}) = S_{j}(x_{j+1}) = a_{j} + b_{j} (x_{j+1} - x_{j}) + c_{j} (x_{j+1} - x_{j})^{2} + d_{j}(x_{j+1} - x_{j})^{3},
\]

para cada $j = 0, 1, \ldots, n-2$.

Puesto que los t'erminos $x_{j+1} - x_{j}$ se utilizar'an varias veces en este 
desarrollo, conviene introducir la notaci'on m'as simple
\[
h_{j} = x_{j+1} - x_{j},
\]
para cada $j = 0, 1, \ldots, n-1$. Si tambi'en definimos $a_{n} = f(x_{n})$, 
entonces la ecuaci'on 

\[
a_{j+1} = a_{j} + b_{j} h_{j} + c_{j} h_{j}^{2} + d_{j} h_{j}^{3},
\]

ser'a v'alida para cada $j = 0, 1, \ldots, n-1$.

De manera an'aloga, defina $b_{n} = S'(x_{n})$ y observe que 

\[
S_{j}'(x) = b_{j} + 2 c_{j} (x - x_{j}) + 3 d_{j} (x - x_{j})^{2}
\]

significa que $S_{j}'(x_{j}) = b_{j}$ para cada $j = 0, 1, \ldots, n-1$. Al 
aplicar la condici'on (4) obtenemos 

\[
b_{j+1} = b_{j} + 2 c_{j} h_{j} + 3 d_{j} h_{j}^{2}
\]

c

Al definir $c_{n} = S''(x_{n})/2$ y aplicar la condici'on (5), se obtiene otra 
relaci'on entre los coeficinetes de $S_{j}$. En este caso, para cada $j = 0, 1, \ldots, n-1$.

\[
c_{j+1} = c_{j} + 3 d_{j} h_{j},
\]

Al despejar $d_{j}$ y sustituir este valro en las ecuaciones anteriores, para cada 
$j = 0, 1, \ldots, n-1$ se obtienen las ecuaciones 

\[
a_{j+1} = a_{j} + b_{j} h_{j} +  (h_{j}^{2}/3) ( 2c_{j} + c_{j+1})
\]

y

\[
b_{j+1} = b_{j} + h_{j} (c_{j} + c_{j+1})
\]

La relaci'on final que incluye los coeficientes se obtienen resolviendo la 
ecuaci'on correspondiente, primero para $b_{j}$,

\[
b_{j} = \frac{1}{h_{j}} (a_{j+1} - a_{j}) - \frac{h_{j}}{3} ( 2c_{j} + c_{j+1})
\]

y entonces, con una reducci'on del 'indice, para $b_{j-1}$:

\[
b_{j-1} = \frac{1}{h_{j-1}} (a_{j} - a_{j-1}) - \frac{h_{j-1}}{3} ( 2c_{j-1} + c_{j})
\]

Cuando sustituimos estos valores en la ecuaci'on de $b_{j+1}$, con el 'idice 
reducido en 1, obtenemos el sistema de ecuaciones lineales

\[
h_{j-1}c_{j-1} + 2 (h_{j-1} + h_{j})c_{j} + h_{j} c_{j+1} = \frac{3}{h_{j}} (a_{j+1} - a_{j}) - \frac{3}{h_{j-1}} (a_{j} - a_{j-1})
\]

para cada $j = 1, \ldots, n-1$.

Este sistema contiene s'olo ${c_{j}}^{n}_{j=0}$ como inc'ognitas, ya que los 
valores de ${h_{j}}^{n-1}_{j=0}$ y de ${a_{j}}^{n}_{j=0}$ est'an dados por el 
espacio de los nodos ${x_{j}}^{n}_{j=0}$ y los valores de $f$ en 'estos.

N'otese que una vez que se conocen los valores de ${c_{j}}^{n}_{j=0}$, encontrar 
el resto de las constantes ${b_{j}}^{n-1}_{j=0}$ y ${d_{j}}^{n-1}_{j=0}$ para 
construir los polinomios c'ubicos ${S_{j}}^{n-1}_{j=0}$ es f'acil.

El interrogante principal que se plantea en relaci'on con esta construcci'on es 
si se pueden determinar los valores de ${c_{j}}^{n}_{j=0}$ y, de ser as'i, si 
estos valores son 'unicos.

Efectivamente si definimos en $f$ en $a = x_{0} < x_{1} < \ldots < x_{n} = b$ 
entonces $f$ tendr'a un interpolante 'unico de trazador natural en los nodos 
$x_{0}, x_{1}, \ldots, x_{n}$; es decir, un interpolante de trazador que cumple 
con las condiciones de frontera $S''(a) = S''(b) = 0$.

La demostraci'on de este teorema no se incluye aqu'i, pero puede encontrarse 
en un libro de an'alisis num'erico como ~\cite{BurFa}.

Mayor informaci'on sobre splines puede encontrarse tambi'en en ~\cite{BurFa}.

\subsection{M'etodo de Gauss}

Para resolver sistemas de ecuaciones lineales se utiliza el m'etodo de Gauss 
con pivoteo total. Este m'etodo se encuentra explicado e implementado en 
~\cite{ChHeRo}.

Vale aclarar que los algoritmos de factorizaci'on pueden simplificarse 
considerablemente en el caso de las matrices de banda, porque una gran cantidad 
de ceros aparecen en ellas en patrones regulares. 

Sin embargo, dada la cantidad de mediciones que se utilizaran (entre 3 y 10), 
el uso de la implementaci'on est'andar del m'etodo de Gauss, no representa un 
disminuci'on significativa de la performance.

\subsection{C'irculo maximal}

Dado un radio $r$, un conjunto de puntos $P$ y una circunferencia $C$ de radio
$r$ diremos que esta es maximal si el conjunto $A_C = P \cap C$ no est'a 
estrictamente incluido en $A_{C'}$ para ninguna circunferencia $C'$ de radio
$r$.

Teorema: Para todo radio $r$, para toda circunferencia maximal $C$ que tiene 
al menos un punto dentro, existe una circunferencia maximal $C'$ tal que 
$A_C=A_{C'}$ y $C'$ tiene un punto sobre su per'imetro. 
Demostraci'on: Si $C$ no tiene ning'un punto sobre su per'imetro,
se la puede desplazar en una direcci'on dada hasta que toque alguno, y ese es
un $C'$ que tiene un punto sobre el per'imetro (por continuidad, ning'un punto
que estaba dentro de $C$ puede ``salir para afuera'' sin antes estar sobre
el per'imetro, y como $C$ era maximal, ning'un punto de afuera puede entrar,
as'i que $A_C=A_{C'}$.

Teorema: Para todo radio $r$, para toda circunferencia maximal $C$ que tiene 
al menos dos puntos dentro, existe una circunferencia maximal $C'$ tal que 
$A_C=A_{C'}$ y $C'$ tiene dos puntos sobre su per'imetro. 
Demostraci'on: Sea $D$ la circunferencia con al menos un punto sobre el 
per'imetro tal que $A_C=A_D$ descripta en el teorema anterior. Si $D$ tiene
m'as de un punto sobre el per'imetro, usando $C'=D$ termina la demostraci'on.
Si no, se puede rotar $D$ para obtener $C'$ en una direccion arbitraria usando 
como centro el punto sobre su per'imetro hasta que alg'un otro punto de dentro 
quede sobre el per'imetro. An'alogamente al teorema anterior, por continuidad 
y maximalidad, $A_C=A_{C'}$.
